def createC1(dataset):
    C1=[]
    for t in dataset:
        for s in t:
            if({s} in C1):
                continue
            else:
                C1.append({s})
    C1.sort()
    return map(frozenset,C1)

def scan(dataset,minisupport=0.6,Ck=None):
    # rst是满足Ck内所有满足最小支持度要求的组合
    rst=[]
    # cutset用于返回Ck内那些被剪枝的组合
    cutset=[]
    # 同时supportData返回了Ck内所有组合的支持度，supportData是一个字典，key是基本元素的组合，而value是这个组合出现的频率
    supportData={}
    for c in Ck:
        for t in dataset:
            if c.issubset(t):
                if c in supportData:
                    supportData[c]+=1
                else:
                    supportData[c]=1
    lenD=float(len(dataset))

    for key in supportData:
        supportData[key]=supportData[key]/lenD
        if(supportData[key]>=minisupport):
            rst.append(key)
        else:
            cutset.append(key)
    return rst,supportData,cutset

# genCj用于输入只含k个元素的若干组合Ck，以及已确定被剪枝的组合列表Cutset,输出含k+1个元素的所有可能的组合Cj。
# 注意要先把前k-1个元素提取出来，然后排序，比较、如果相等后t不含有cutset的元素 再把合并后的加入。
def genCj(Ck,k,Cutset={}):
    lenCk=len(Ck)
    Cj=set()
    for i in  range(lenCk):
        for j in range(i+1,lenCk):
            l1=list(Ck[i])[:k-1]
            l2=list(Ck[j])[:k-1]
            l1.sort()
            l2.sort()
            if(l1==l2):
                t=Ck[i]|Ck[j]
                f=0
                for each in Cutset:
                    if set(each).issubset(t):
                        f=1
                        break
                if(f==0):
                    Cj.add(t)
    return Cj
    
def apriori(dataset,minisupport=0.6):
    #from number i layer frequent item set generate i+1 th frequent item set.
    C1=createC1(dataset)
    Ck=C1
    k=1
    supportData={}
    CutSet=[]
    rstC=[]
    while Ck!=set():
        rst,support,cutset=scan(dataset,minisupport,Ck)
        rstC += rst
        supportData.update(support)
        CutSet.append(cutset)
        Cj=genCj(rst,k,CutSet)
        k+=1
        Ck=Cj

    return rstC,supportData

# 输入菜谱 数组 ， 输出 字典{frozenset(菜):float(支持度)}
def get_support(data):
    rstC,supportData=apriori(data,minisupport=0.6)
    return supportData


# 输入 菜 id ，supportData ，输出 和 菜 id 关联度 又高到底 的 list(菜)
def tuijian(s,supportData):
    res = []
    for key in supportData:
        if s in key and len(key)!=1:
            res.append(key)
    result = reversed(sorted(res,key=lambda x:supportData[x]))
    result1 = []
    for i in result:
        for j in i:
            if j!=s and j not in result1:
                result1.append(j)
    return result1

# 相似度推荐 输入 用户选择的 菜 ，全部菜谱， 输出 按 重复率 由高到低 与 对应的菜谱
def xiangshidu(user,pkg_list):
    xiang = []
    for each in pkg_list:
        x = len(set(user)&set(each))/len(each)
        xiang.append((each,x))
#     sorted(xiang,key=lambda x:x[1])
    xiang.sort(key=lambda x: x[1], reverse=True)
    return xiang

